A field solver solves a Laplace equation in a large 3D domain of integrated circuit (IC) design, consisting of conductor nets and surrounding dielectric stacks, to find an electric field. The flux of an electric field through a closed surface around a conductor, divided by applied bias gives a parasitic coupling capacitance between the conductor and its neighbors. However, field solvers that operate based on mesh discretization methods, such as finite volume, finite element or boundary element methods, are not capable of handling the very large domain of IC design, in spite of a large amount of research. The most promising technique for parasitic capacitance extraction is a random walk Monte Carlo field solver, which relies on statistical methods to solve a Laplace equation, and does not rely on mesh discretization.
Parasitic capacitance extracted using a random walk Monte Carlo field solver is currently regarded as a gold standard and is used for validation of other, less exact models. Parasitic capacitance of some critical nets of an IC design, as well as parasitic capacitance of small IC designs (where high accuracy is important) may be extracted completely by a random walk Monte Carlo field solver, without relying on approximate models. With IC designs getting more and more complicated, it is highly desirable to use a random walk Monte Carlo field solver as the only parasitic capacitance extraction tool. The main obstacle to achieve this is the relatively poor performance of a random walk Monte Carlo field solver, compared to simpler models.
A random walk Monte Carlo field solver has been proposed by LeCoz, et al. in “A Stochastic Algorithm for High Speed Capacitance Extraction in Integrated Circuits”, Solid State Electronics, 35, 1992, pp. 1005-1012. FIG. 1 is a block diagram illustrating steps conventionally used by a random walk Monte Carlo field solver to determine the parasitic capacitance of an origin net 101 of an IC design 100. First, a closed Gaussian surface 105 is created around an origin net (conductor) 101 whose parasitic capacitance is to be extracted. A point P1 is then chosen randomly on the Gaussian surface 105, and a cube 111 is built with the center at the location of point P1, such that there is no metal present inside the cube 111. An edge of the cube 111 may coincide with an edge of the origin net 101 as illustrated by FIG. 1, although this is not necessary. The value of the weight of the random walk is determined by the size of the cube 111 and a dielectric constant at the point P1. Using a probability distribution function, a new point P2 on the surface of the cube 111 is sampled randomly. This probability distribution function uses the absolute value of the normalized Green's function of the normal component of an electric field for Laplace equation in the cube 111. This probability distribution function is hereinafter referred to as the electric field Green's function. The sign of the value provided by the electric field Green's function determines the sign of the weight of the random walk. A new cube 112 is built with the center at the location of point P2, such that there is no metal present inside the cube 112 (but there is metal (e.g., target net 123) present at an edge of the cube 112). Using a probability distribution function, a new point P3 on the surface of the cube 112 is chosen randomly. This probability distribution function uses the electrostatic potential Green's function of Laplace equation in the cube 112. This probability function is hereinafter referred to as the electrostatic potential Green's function. The last step, which requires the electrostatic potential Green's function, is repeated, until a new point is located on a surface of a metal. In the illustrated example, cube 113 (which shares an edge with target net/conductor 121) is formed around point P3, point P4 is randomly selected on cube 113, cube 114 (which shares an edge with target net/conductor 122) is formed around point P4, and point P5 is randomly selected on cube 114, wherein point P5 is located on a surface of target net conductor 122, thereby ending the random walk. The weights of random walks terminated on all conductors (e.g., target nets 121-123) are multiplied by 1 Volt, except for those terminated on the originating conductor (origin net 101) which are multiplied by 0 Volts and thus are discarded. Each of the weights is added as a contribution to a first sum, and the square of each of the weights is added to a second sum. The first sum, averaged over all random walks is the mean value of the coupling capacitance (hereinafter referred to as “the mean value”) between origin net 101 and target nets 122-123. The second sum, averaged over all walks and subtracted from the mean value squared provides a sample variance of the coupling capacitance (hereinafter referred to as “the sample variance”). A sample variance is a statistical approximation to the true variance, which is an unknown constant characterizing the population of random walks. As the simulation progresses, the sample variance, while changing its value, becomes a better and better approximation and eventually converges to the true variance. The manner in which the random walks are performed may strongly affect the value of the true and sample variances. The sample variance divided by the number of walks is the variance of the mean value. The square root of the variance of the mean value is the standard deviation of the mean value. The statistical error of the mean value is the standard deviation of the mean value divided by the mean value. As the number of random walks increases, the statistical error of the mean value, the variance of the mean value and the standard deviation of the mean value converge to a zero value, thus improving a confidence in the mean value of the coupling capacitance. The rate of the convergence depends on the value of the sample variance, i.e. on the manner the random walks are performed.
The simulation is done iteratively, with an equal number of random walks spent on each iteration, and the statistical error of the mean value being computed at the end of each iteration. The simulation continues until the statistical error of coupling capacitance to each neighboring net decreases sufficiently to meet a certain accuracy goal. When the accuracy goal is met, the coupling capacitance is said to be converged. Although the statistical error is used to check the accuracy goal, analogous convergence goals can be established for variance of the mean value or standard deviation of the mean value. Minimizing any one of these three quantities, will also minimize the other two.
The runtime of the process described above depends on the statistical variance of the mean value of the coupling capacitance and is directly proportional to the number of random walks.
The performance of the above-described random walk Monte Carlo field solver is poor (slow) because many random walks are inevitably performed from low-error/low-contribution areas of the Gaussian surface 105. The performance of the above-described random walk Monte Carlo field solver is also poor because a relatively large number of the random walks are inevitably performed to determine the coupling capacitances of nearby neighboring nets (conductors) that have already converged. At the same time, the random nature of the walks ensures that high-error/high-contribution areas do not get sufficient coverage. That is, a relatively small number of the random walks are performed to determine the coupling capacitances that have not yet converged.
The conventional random walk Monte Carlo field solver also exhibits poor performance due to the fact that the mean value of the coupling capacitance is composed of both positive and negative contributions of random walks (due to the positive and negative signs provided by the electric field Green's function). These positive and negative contributions can result in a convergence that is slow and oscillatory, particularly when the mean value of the coupling capacitance is very small.
It would therefore be desirable to have a method and structure that solves the problem of poor performance of parasitic capacitance extraction using a conventional random walk Monte Carlo field solver.